As is known, a MANET network is a packet network formed by a plurality of nodes, which communicate with each other via ad hoc links. The nodes therefore cooperate with each other to correctly route packets by applying relay techniques of a multi-hop type.
In practice, MANET networks are generally characterized by the mobility of the nodes that form them, as well as by the absence of fixed infrastructures able to ensure communications between the nodes. Therefore, MANET networks are typically implemented inside extremely dynamic environments on an as-needed basis. For example, MANET networks are known that are employed in the automotive field, where they are also known as vehicular ad hoc networks (VANET).
Over time and on the basis of the typical characteristics of MANET networks, routing protocols have been proposed that are capable of ensuring communications between the nodes. For example, the so-called Optimized Link State Routing Protocol (OLSR protocol) is known, as defined by the Internet Engineering Task Force (IETF) and described, for example, at Internet address http://www.rfc-editor.org/rfc/rfc3626.txt.
An implementation of the OLSR protocol is described, for example, in “Optimized Link State Routing Protocol for Ad Hoc Networks”, by P. Jacquet et al, Hipercom Project, INRIA Rocquencourt, BP 105, 78153 Le Chesnay Cedex, France.
The OLSR protocol is a proactive type of protocol, based on the exchange of control packets between the nodes, these packets being periodically transmitted in broadcast mode. In other words, when a generic node sends its control packet, it addresses this packet to all the other nodes of the network; consequently, all of the nodes visible to the generic node, i.e. capable of receiving the electromagnetic signals transmitted by the generic node, receive and process this packet. The broadcast transmission contemplates that the sent packet contains a specific address, also known as a broadcast address, known to all the nodes of the network.
In particular, the OLSR protocol is characterized by the fact that the control packets transmitted by the nodes are very small, as well as for the fact that only some nodes of the network retransmit, namely relay the received control packets, retransmission still taking place in broadcast mode. In this regard, although each retransmission implies, at physical level, a transmission, in general one refers to the transmission or generation of a packet to indicate the first generation of the packet and the associated content by a first node, while one refers to the retransmission of the packet to indicate retransmission of the packet, which contemplates a modification to just the header of the packet, but not the data contained therein, the latter also being known as the message. In any case, while the verb “to retransmit” implies an effective retransmission, the verb “to transmit” can also be used to refer to the action of transmitting a packet during a retransmission, and so its use is not necessarily limited to the transmission of a packet by the first node that has generated the packet. Similarly, the verb “to send” is also used to refer to the action of transmitting or retransmitting a packet without distinction. Again, the action of generating a packet is also known as originating a packet, while the action of communicating a packet to a node disregards the fact of whether the node is near or far, ad so disregards the fact of whether the communication takes place in a direct or indirect manner.
In the event of link faults or interruptions, the OLSR protocol does not generate any additional traffic with respect to the already mentioned control packets. In addition, the OLSR protocol works in a completely distributed manner and does not need any central entity. In addition, the OLSR protocol does not require that the control packets are received by the nodes in exactly the same order of transmission; this is due to the fact that each node signs its control messages with a progressive sequence identifier.
In detail, each node selects, from its neighbours, or rather the nodes that are just one hop away from it, a set of multipoint relays. In general, the proximity of two nodes does not implicate the existence of a bidirectional link between them, but implies the presence of a link that is at least one-way, and therefore implies that at least one of these two nodes is able to directly receive packets sent by the other node, without the packets having to be retransmitted by a third node. That having been said, considering one node, only the neighbouring nodes of the node considered and connected to it by bidirectional links can be selected as multipoint relays of the node considered.
Referring to a generic node N, and indicating the corresponding set of multipoint relays as MPR(N), each node of the MPR(N) set, when it receives a control packet transmitted by node N, reads and processes the control packet, and subsequently retransmits the control packet, still in broadcast mode. Conversely, the neighbouring nodes of node N that do not belong to the MPR(N) set, read and process the control packets sent by node N, but do not retransmit them. Each node of the MANET network stores and then updates a list of so-called MPR selectors. In particular, with reference, for example, still to node N, its list of MPR selectors is formed by nodes that are neighbours to it and that have selected it as their multipoint relay.
Given, for example, still node N, the selection of the set of multipoint relays takes place such that all the nodes that are two hops away from node N are connected to it via the multipoint relays, where a connection is intended as being over a bidirectional link. Therefore, the union of nodes neighbouring the multipoint relays contains all the nodes that are two hops away from node N. The smaller the cardinality of the set of multipoint relays, the better the operation of the OLSR protocol.
More in particular, given, for example, still node N, the selection of the set of multipoint relays takes place based on the so-called “willingness” parameter, which indicates a sort of disposition that each one of the neighbouring nodes of node N has to becoming a multipoint relay. A procedure for the selection of the multipoint relays based on willingness is described in “Request For Comments” (RFC) 3626 of the Internet Engineering Task Force. This procedure envisages that each node sets its own willingness to an integer value between zero and seven and that it communicates the set value to the other nodes, through so-called HELLO packets. Furthermore, still with reference to node N, the selection of its multipoint relays takes place in way that the nodes neighbouring it and having a willingness of seven are definitely selected as multipoint relays, and the nodes neighbouring it and having a willingness of zero are not selected as multipoint relays; the neighbouring nodes of node N that have a willingness of between one and six are instead selected with a priority proportional to the willingness value that has been set, until the set of multipoint relays is completed.
The control packets include the aforementioned HELLO packets, which, unlike other control packets, are not retransmitted by any node of the MANET network, not even by the multipoint relays.
In particular, again given node N, this periodically transmits its own HELLO packets. Each HELLO packet contains a control header, which comprises the address of the node that has transmitted the HELLO packet. In addition, each HELLO packet contains:                a list of the addresses of the neighbouring nodes of node N and connected to node N via bidirectional links;        a list of the addresses of the neighbouring nodes of node N, which have been heard by node N, i.e. to which node N is connected via a one-way links;        a list of the multipoint relays of node N; and        a sequence number associated with the HELLO packet.        
For completeness, the aforementioned lists present in the HELLO packet can be partial, provided that all the neighbouring nodes are indicated in HELLO packets transmitted within a given time interval by the node N. Furthermore, three different indications are used to indicate the state of the links, which respectively correspond to one-way, bidirectional and multipoint relay. In addition, to check a link with any neighbouring node Y as being bidirectional, node N detects the possible reception of a HELLO packet sent by node Y and containing the address of node N.
Each node is therefore able to determine, on the basis of the HELLO packets it receives, its own MPR selectors, the addresses of which are stored in a table of MPR selectors.
Each node, on the basis of the HELLO packets it receives, is able to have knowledge of the links with nodes that are up to two hops away. In particular, again with reference to node N, this is able to maintain a neighbour table, in which it stores a plurality of entries, each entry containing the address of a corresponding node that is one hop away (neighbouring node), as well as the state of the connection with that neighbouring node and a list of the addresses of the nodes that are two hops away from node N and which are neighbours of this neighbouring node. The neighbour table also contains a sequence number, which indicates the most recent set of multipoint relays selected by node N. Each time that node N communicates its set of multipoint relays (as described hereinafter) to the other nodes, it also increments this sequence number. Furthermore, all the entries of the neighbour table are associated with corresponding holding times, the expiry of which results in the entries being deleted.
Each node is therefore able to select, on the basis of its own neighbour table, its own set of multipoint relays, such that it satisfies the previously mentioned requirements. This set of multipoint relays will be communicated in subsequent HELLO packets that will be transmitted. In particular, selection of the set of multipoint relays for node N is carried out each time node N detects a change in its neighbouring nodes, due, for example, to a fault on a bidirectional link, or the addition of a bidirectional link with a new node; furthermore, node N performs a new selection each time it detects a change in the nodes two hops away from it and which are connected to it through bidirectional links. Therefore, each node updates its own multipoint relays on every reception of a HELLO packet.
In greater detail, at a time t1, the union of the nodes neighbouring the multipoint relays of node N contains all the nodes that are two hops away from node N, assuming that the information contained in the neighbour table of node N corresponds to the links present at time t1 between node N and the nodes that are up to two hops away from node N. In other words, the information contained in the neighbour table are at the most related to a time t0, prior to time t1, when it is possible that the aforementioned statement regarding the union of the neighbouring nodes is temporarily untrue, due, for example, to the approach of node unknown to node N. In any case, the aforementioned statement becomes true in steady state, or when, still given node N for example, the changes in the respective set of its neighbouring nodes are slow with respect to the times with which the nodes transmit the HELLO packets.
Still with reference to the MPR selector table, the addresses of the MPR selectors contained therein are associated with corresponding sequence numbers, which are equal to the sequence numbers stored precisely by the MPR selectors and communicated by means of the HELLO packets. Furthermore, the entire MPR selector table is associated with a corresponding MPR selector table sequence number, which is equal to the most recent sequence number associated with a HELLO message that has been received and which has caused a change in the MPR selector table.
The control packets further comprise so-called topology control (TC) packets, which are periodically transmitted by the multipoint relays in broadcast mode.
Still with reference, by way of example, to node N, each TC packet that it transmits contains:                the address of the node that originated it;        the set of its MPR selectors; and        the MPR selector table sequence number, which is precisely associated with its own MPR selector table.        
In particular, the list of MPR selectors contained in the TC packet can be partial, provided that the complete list is sent, via two or more TC packets, within a certain refresh period. Furthermore, the time interval between the transmission of two successive TC packets depends on the fact of whether or not the MPR selector table is modified. For example, in the case of MPR selector table modification, node N can transmit a new TC packet as soon as a minimum period after sending the previous TC packet has lapsed; subsequent TC packets can then be transmitted with a given periodicity, until a new change to the MPR selector table takes place.
On the basis of the TC packets received, the nodes build and update their own topology tables, in which they store information regarding the multipoint relays of the other nodes. In particular, still assuming to refer to node N, its topology table comprises one or more entries, each entry comprising:                an address of a possible destination, namely the address of a MPR selector contained in a TC packet received by node N;        a last-hop address related to the aforementioned possible destination, which is equal to the address of the node that has sent the aforementioned TC packet received by node N;        the corresponding MPR selector table sequence number of the node that has sent the aforementioned TC packet received by node N; and        a corresponding holding time, after which the entry is deleted.        
In practice, the presence, inside the topology table, of an entry related to a given node indicates the possibility of reaching the given node by sending a packet to the node whose address is equal to the last-hop address contained in the entry. However, it should be noted that there could be several entries inside the topology table having a same possible destination address, but with different last-hop addresses.
More in particular, upon reception of a TC packet sent by a sending node, node N (for example) performs the following operations:                checks whether there is an entry in its topology table in which the last-hop address is equal to the address of the sending node and, if so, whether the MPR selector table sequence number contained in this entry is greater than the MPR selector table sequence number contained in the TC packet received, in which case the TC packet is rejected without any further processing;        in the case where the aforementioned entry exists, if its last-hop address is equal to the address of the sending node and the MPR selector table sequence number contained in this entry is less than the MPR selector table sequence number contained in the TC packet received, this entry is deleted;        for each MPR selector address indicated in the TC packet received, node N checks whether a destination is present in its topology table that has an address equal to the MPR selector address considered, and whether the corresponding last-hop address is equal to the address of the sending node, in which case the corresponding holding time is reset to an initial (predetermined) value; in all other cases, node N creates a new entry in its topology table, which corresponds to the MPR selector address considered.        
Each one of the nodes of the MANET network also maintains its own routing table, which is built and updated on the basis of the TC packets received, and more particularly on the basis of the topology table. The routing table stores information regarding the paths, i.e. the sets of successive and connected links that enable reaching the corresponding destinations.
Still making reference, for example, to node N, its routing table comprises one or more entries, each of which includes:                an address of a corresponding destination;        a next-hop address, namely the address of a neighbouring node of node N, to which it is necessary to send a packet, if this packet is destined to the node having an address equal to the aforementioned address of a corresponding destination, which is also referred to as the destination node; and        a distance estimate, or rather an estimate of the number of hops to reach the destination node.        
In practice, there is a bidirectional path between the node N and the destination node that passes through the node having an address equal to the next-hop address.
Each time node N receives a TC packet, for each destination address contained therein, it stores/updates a corresponding [last-hop, node] pair, which is actually formed from the destination address ([node]) and the address of the node that has sent the TC packet ([last-hop]). On the basis of the [last-hop, node] pairs, which are also referred to as connected pairs, node N determines, given a destination node, the corresponding path for reaching it. To this end, given for example a destination node R, node N searches for a connected pair [X,R], and successively for a connected pair [Z,X], and so on, until it finds a node K that is part of the MPR(N) set of multipoint relays of node N. The next-hop address related to the entry regarding destination R contained in the routing table of node N is thus equal to the address of node K.
Node N recalculates its routing table each time it detects a change in its neighbour and topology tables.
In greater detail, to calculate (or recalculate) the routing table, node N can execute the following algorithm.
Initially, all the entries possibly present in the routing table are deleted. Then, the new entries are stored, starting from those that have neighbouring nodes of node N as destinations. In particular, in the case where these neighbouring nodes are connected to node N in bidirectional mode, the corresponding entries contain destination and next-hop addresses that are the same, as well as having distance estimates equal to one.
Then, entries regarding nodes that are distanced from node N by distances h+1, where h=1, are stored.
In particular, node N stores a corresponding entry for each entry in the topology table that i) includes a destination address that does not correspond to the destination address of any of the entries present in the routing table, and ii) the last-hop address of which corresponds to the destination address of an entry in the routing table with a distance estimate equal to h. This corresponding entry contains a destination address equal to the destination address of the entry in the topology table, and a next-hop address equal to the next-hop address of the entry in the routing table, the destination address of which is equal to the aforementioned last-hop address.
Then, node N sets h=h+1 and repeats the previously specified operations. In this way, node N arrives at determining its own routing table.
With regard to data traffic, the OLSR protocol is of the so-called unicast type, i.e. provision is made that, if a node, for example node N, needs to transmit a data packet to another node W, this node transmits the data packet to the node (for example, G) whose address is equal to the next-hop address contained in the entry in the routing table having a destination address that coincides with the address of the node W. To this end, node N inserts both the address of node W and the address of node G in the data packet, these still being referred to, respectively, as the destination address and the next-hop address. Furthermore, since node N originates the data packet, it inserts its own address in the data packet, which is also referred to as the source address; this last address, like the destination address, is not modified during the course of the retransmissions. In general, reference is made to the transmission (or retransmission) of the data packet from node N to node G to indicate that the packet is transmitted (or retransmitted) from node N and contains the address of node G as the next-hop address, and therefore it is physically received by all the neighbouring nodes of node N, but all the neighbouring nodes of node N, except node G, reject the data packet, or in any case, according to the multiple access technique adopted, are unable to interpret the data packet.
The data packet is then received by all the neighbouring nodes of node N, but only node G processes the data packet and retransmits it to the node (for example, L) the address of which is equal to the next-hop address contained in the entry of the routing table of node G having a destination address that coincides with the address of the node W. The procedure is then repeated, until the data packet is received by node W.
Still with reference to the data traffic, according to the OLSR protocol, a node may transmit a data packet to a neighbouring node only if it is connected to the latter through a bidirectional link.
That having been said, there are other known types of protocol, such as, for example, the so-called Simple Multicast Forwarding Protocol (SMF protocol), defined by the Internet Engineering Task Force and described, for example, in the so-called fourteenth version at Internet address http://tools.ietf.org/html/draft-ieft-manet-smf.14.
For the distribution of data traffic, the SMF protocol makes use of the same signalling distribution employed by the OLSR protocol. In other words, in accordance with the SMF protocol, the data packets are transmitted in broadcast mode in the same way as the TC packets in the OLSR protocol. Therefore, the SMF protocol also contemplates, among other things, the determination of multipoint relays.
In detail, still referring to node N, this transmits its own data packets in broadcast mode. In addition, given any node of the MPR(N) set, when it receives a data packet transmitted from node N, it reads and processes the data packet, and then retransmits the data packet, still in broadcast mode. Conversely, the nodes that are neighbours of node N, but which do not belong to the MPR(N) set, read and process the data packets transmitted by node N, but do not retransmit them.
The SMF protocol also provides for an identification mechanism for duplicated data packets, such as, for example, the calculation of a hash function, or the introduction of a data packet sequence number in each data packet. In this way, given any node that is a multipoint relay, this cannot retransmit a data packet more than once, so as to avoid forming a loop.
More in particular, the SMF protocol furthermore envisages that the data packets can also be transmitted in multicast mode, or rather that it is possible to transmit data packets to a predetermined group of nodes. The multicast transmission of data packets is the same as the broadcast transmission of data packets, namely provides that the data packets are transmitted in broadcast mode and retransmitted only by the multipoint relays, but it also provides that if a node not belonging to the group receives a data packet, it then rejects the data packet without processing it.
In practice, also in the case of multicast transmission, the SMF protocol envisages an underlying broadcast transmission, the multicast transmission consequently being achieved through opportune programming of the protocol stacks of the nodes in the network.
The SMF protocol therefore enables distributing data packets in multicast mode; however, it is not optimized for this mode of operation.
Further examples of SMF and OLSR protocols are respectively disclosed in Macker J. et al., “Simplified Multicast Forwarding, rfc6621”, Internet Engineering Task Force, Standard, Internet Society (ISOC) 4, Rue Des Falaises CH-1205, Geneva, Switzerland, 18 May 2012, pages 1-55 and Clausen T., “Combining Temporal and Spatial Partial Topology for MANET routing—Merging OLSR and FSR”, Proceedings of IEEE Conference on Wireless Personal Multimedia Communications”, 1 Oct. 2003, Yokosuka, Japan.